package com.leecode;

import java.util.Arrays;

/**
 * 用自己的思路:和求两列围成的最大面积类似,
 * 我:把maxH优化后5%,85%
 */
public class Leet42 {
	public static void main(String[] args) {
		System.out.println(new Leet42().trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
		System.out.println(new Leet42().trap(new int[]{2, 0, 2}));
	}

	public int trap(int[] height) {
		if (height.length <= 2) return 0;
		int maxH = 1;
		int sum = 0;

		for (int i = 0; i < height.length; i++) {
			if (height[i] > maxH) maxH = height[i];
		}

		int moveB = 0;
		int moveE = height.length - 1;
		int lastWaterHeight=0;
		int[] temp = Arrays.copyOf(height, height.length);
		Arrays.sort(temp);
		h:
		for (int a = 0; a < temp.length - 1; a++) {
//		可以,但maxH很大时,会超时,
//		for(int i=1;i<=maxH;i++){
			int i = temp[a];
			while (moveB <= height.length - 1) {
				if (height[moveB] < i) {
					moveB++;
					continue;
				} else {
					while (moveE > moveB) {
						if (height[moveE] < i) {
							moveE--;
							continue;
						} else {
							for (int l = moveB + 1; l < moveE; l++) {
								if (height[l] < i) {
									sum += i-Math.max(height[l],lastWaterHeight);
								}
							}
							lastWaterHeight=i;
							continue h;
						}
					}
					return sum;
				}
			}
			return sum;
		}

		return sum;
	}
}
